(load 'grafo)
(load 'calles)

(defun GPS_MIN(i f)
	(TRADUCIR (MENOR (GPS i f)))
)

(defun GPS_COMP(i f)
	(MAX_MIN_LIST (GPS i f))
)


(defun GPS ( i f &OPTIONAL (CAMINOS (LIST (LIST i))) )
	(IF (NULL CAMINOS) NIL
		(IF (TRABADOS CAMINOS f) (MAPCAR 'REVERSE (LLEGARON CAMINOS f))
			(GPS i f (AVANZARLOS CAMINOS f))
		)
	)
)

(defun MAX_MIN_LIST (L)
	(LIST (MENOR L) (MAYOR L) L)
)

(defun MENOR(L)
	(IF (< (LENGTH L) 2) (CAR L)
		(IF (< (LENGTH (CADR L)) (LENGTH (CAR L))) (MENOR (CONS (CADR L) (CDDR L)) )
			(MENOR (CONS (CAR L) (CDDR L)))
		)
	)
)

(defun MAYOR(L)
	(IF (< (LENGTH L) 2) (CAR L)
		(IF (> (LENGTH (CADR L)) (LENGTH (CAR L))) (MAYOR (CONS (CADR L) (CDDR L)) )
			(MAYOR (CONS (CAR L) (CDDR L)))
		)
	)
)

(defun LLEGARON (CAMINOS f)
	(IF (NULL CAMINOS) NIL
		(IF (EQ (CAAR CAMINOS) f) (CONS (CAR CAMINOS) (LLEGARON (CDR CAMINOS) f))
			(LLEGARON (CDR CAMINOS) f)
		)
	)
)

(defun TRABADOS (CAMINOS f)
	(IF (NULL CAMINOS) T
		(IF (TRABADO (CAR CAMINOS) f) (TRABADOS (CDR CAMINOS) f)
			NIL
		)
	)
)

(defun TRABADO (CAMINO f)
	(IF (EQ (CAR CAMINO) f) T
		(EQ (LENGTH(DIFERENCIA (VECINOS (CAR CAMINO) GRAFO) CAMINO)) 0)
	)
)

(defun AVANZARLOS (CAMINOS f)
	(IF (NULL CAMINOS) NIL
		(APPEND (AVANZARLO(CAR CAMINOS) f) (AVANZARLOS(CDR CAMINOS) f))
	)
)

;Avanza cada camino, agregando el nuevo paso, si hay mas de un paso posible, genera dos caminos
(defun AVANZARLO (CAMINO f)
	(IF (NULL CAMINO) NIL
		(IF (EQ (CAR CAMINO) f) (LIST CAMINO)
			(MAPCAR '(LAMBDA(X) (CONS X CAMINO)) (DIFERENCIA (VECINOS (CAR CAMINO) GRAFO) CAMINO))
		)
	)
)

(defun VECINOS (A G)
	(IF (NULL G) NIL
		(IF (EQ A (CAAR G)) (CADAR G)
			(VECINOS A (CDR G))
		)
	)
	
)

(defun EXISTE (A L)
	(IF (NULL L) NIL
		(IF (EQ A (CAR L)) T
			(EXISTE A (CDR L))
		)
	)
)

(defun DIFERENCIA (A B)
	(DIFERENCIAR A B NIL)
)

(defun DIFERENCIAR (A B R)
	(IF (NULL A) R
		(IF (EXISTE (CAR A) B) (DIFERENCIAR (CDR A) B R)
			(DIFERENCIAR (CDR A) B (APPEND R (LIST (CAR A))))
		)
	)
)